//https://leetcode.cn/problems/basic-calculator/description/

class Solution {
public:
    unordered_map<char, int> mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    void toRPN(const string& s, size_t& i, vector<string>& v) {
        stack<char> st;
        while (i < s.size()) {
            if (isdigit(s[i])) {
                string num;
                while (i < s.size() && isdigit(s[i])) {
                    num += s[i];
                    i++;
                }
                v.push_back(num);
            } else if (s[i] == '(') {
                i++;
                toRPN(s, i, v);
            } else if (s[i] == ')') {
                while (!st.empty()) {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
                i++;
                return;
            } else{
                if (!st.empty() && mp[st.top()] >= mp[s[i]]) {
                    v.push_back(string(1, st.top()));
                    st.pop();
                }
                st.push(s[i]);
                i++;
            }
        }
        while (!st.empty()) {
            v.push_back(string(1, st.top()));
            st.pop();
        }
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto& e : tokens) {
            if (!(e == "+" || e == "-" || e == "*" || e == "/")) {
                st.push(atoi(e.c_str()));
            } else {
                int a = st.top();
                st.pop();
                int b = st.top();
                st.pop();
                switch (e[0]) {
                case '+':
                    st.push(a + b);
                    break;
                case '-':
                    st.push(b - a);
                    break;
                case '*':
                    st.push(a * b);
                    break;
                case '/':
                    st.push(b / a);
                    break;
                }
            }
        }
        return st.top();
    }
    int calculate(string s) {
        string news;
        for(auto& e: s){
            if(e!=' '){
                news+=e;
            }
        }
        news.swap(s);
        news.clear();
        for(size_t i=0;i<s.size();i++)
        {
            if(s[i]=='-'&&(i==0||(!isdigit(s[i-1])&&s[i-1]!=')'))){
                news+="0-";
            }else{
                news+=s[i];
            }
        }
        vector<string> v;
        size_t i=0;
        toRPN(news,i,v);
        return evalRPN(v);
    }
};